The process of designing chips involves many steps. Near the beginning of the process is a step of defining an overall chip architecture. That involves definition of units, with specific functions, that perform the desired functions of the chip. Some types of functions are processing, interfacing to other chips, and transporting information within the chip. All such functions are interesting, but particularly the functions for transporting information within the chip. Those are interesting because they require long connections across the floorplan of the chip.
A later step in the process of design chips is place and route (P&R). P&R is a slow step. It is done by software tools that, within the floorplan, piece together the logic and storage cells that make up a chip design. The software tools that do P&R take as input a floorplan description file and a netlist that describes the required connections between cell instances and their function. The P&R tool finds a unique placement location for each cell based on their sizes and connectivity. Placement has a goal of minimizing the total length of wires needed to make all cell connections within the chip, which generally eases the routing of wires between cells. The P&R tool also calculates and considers the logic gate switching delay along paths between flops as well as the signal propagation delay between flops, and adjusts placement in an attempt to ensure that no delay exceeds the target clock period of the flops operation.
Most P&R tools operate iteratively. That is, they make incremental changes, and calculate the resulting wire length effect, timing delay, and other design characteristics. The best P&R tools today are quadratic or linear placers. Such placers solve the equivalent of a spring problem. That is, where connection points would settle if all connections were springs. A change in the placement of any one cell affects the wire length and delay of many other cells. Modern chips have many millions of cells. Even on very fast computers, the P&R process takes a very long time. The duration of P&R for a chip is significantly longer if the timing constraints are tight, and even worse so if the starting point initial placement, before incremental changes, is uncoordinated. A better initial starting point saves a lot of time in computing a solution that meets constraints and conforms to design rules.
A problem for conventional P&R tools is how to create an initial placement that will minimize the number of incremental changes needed to achieve a successful design that meets timing constraints while minimizing wire length. Conventional P&R tools do not use information about the overall chip architecture. These tools place a netlist of cell instances without regard for the architectural functionality that a synthesis tool used to create the P&R input netlist.
A further problem with conventional P&R tools is that they primarily optimize placement in order to minimize wire length. Timing calculations of the effect of incremental placement changes are more complex and take longer than wire length calculations. Therefore, to achieve a result in a shorter amount of time, P&R tools put more effort into placement, and might achieve placement results that are unfavorable to timing. When the target speed is high, the later steps in the design process, such as post-placement routing, clock tree insertion, and power net insertion, might result in a design that cannot meet timing requirements if the placer moves cells to unfavorable positions.
Timing problems in large chips occur between clocked registers. Distance between these registers has minimum time of flight defined by the wire characteristics and buffering. Since wires are composed of metal, and metal has resistance, optimal delay across a large span has to be minimized using periodic buffer insertion. Optimal buffer placement across a wire path between two clocked registers defines the minimum time a signal can travel between them. By deduction, placement distance between registers limits performance. Timing paths optimized by Place and Route occur between registers only. Hence, these systems ability to move registers and optimize their placement is limited.